#ifndef _RED_BLACK_TREE_H_
#define _RED_BLACK_TREE_H_

#include <stdio.h>
#include <stdlib.h>

// 定义红黑树节点颜色
typedef enum { RED, BLACK } Color;

// 红黑树节点结构体
typedef struct rb_node {
    int key;
    Color color;  // 节点颜色，0表示红色，1表示黑色
    struct rb_node *left;
    struct rb_node *right;
    struct rb_node *parent;
} rb_node;

// 红黑树结构体，包含根节点指针（初始为哨兵节点）
typedef struct rb_tree {
    rb_node *root;
    rb_node *nil;
} rb_tree;

rb_node* create_rb_node(int key);
rb_tree * create_rb_tree();
void left_rotate(rb_tree *tree, rb_node *node);
void right_rotate(rb_tree *tree, rb_node *node);
void insert_fixup(rb_tree *tree, rb_node *new_node);
void insert(rb_tree *tree, int key);
rb_node* search(const rb_tree *tree, int key);
rb_node * minimum(const rb_tree *tree, rb_node *node);
rb_node * maximum(const rb_tree *tree, rb_node *node);
rb_node* successor(const rb_tree *tree, rb_node *node);
rb_node * predecessor(rb_tree *tree, rb_node *node);
void delete_fixup(rb_tree *tree, rb_node *node);
void delete_node(rb_tree *tree, rb_node *node_to_delete);
void inorder_traversal(rb_node *node);
void transplant(rb_tree *tree, rb_node *original, rb_node *replacement);
void destroy_rb_tree(rb_tree *tree);
void destroy_rb_tree_helper(rb_node *node);

#endif